1. Field of the Invention
The present invention relates to the field of random number generation, more particularly to the field of pseudorandom number generation.
2. Description of Related Art
Random numbers have a variety of uses; for example, the use of random numbers is prevalent in applications such as cryptography, testing of digital circuits and telecommunication systems. However, one common issue is how the random numbers are generated. Typically an initial value (commonly referred to as a seed value) is used to provide an input to algorithm. The algorithm then outputs a number based on the seed value. As can be appreciated, one potential issue with this approach is that if the algorithm and the seed value are known, the resultant random number can be predicted (and thus is not actually random).
One method of overcoming this issue is to use random seed values based on, for example, atmospheric noise. This tends to be somewhat complex, however, and therefore is less suitable for many systems where cost and/or access to atmospheric noise (or the equivalent) is an issue. Therefore, it is relatively common to use a pseudorandom number generator (PRNG) algorithm that can provide a random number without requiring a completely random seed value. While a PRNG algorithm provides the same output for a given input, if the seed value and/or other inputs are obscured then resultant random value will have the appearance of being random to an observer.
Therefore, PRNGs attempt to provide a value that is not easily predicted based on a seed value that may or may not be known. Known examples of PRNGs include a linear feedback shift register (“LFSR”) and linear congruent generator (“LCG”). One theoretical issue with linear algorithms is the potential for patterns to emerge, thus making such algorithms less suitable for applications such as cryptology.
Nonlinear generators such as the known Blum, Blum and Shub generator have also been proposed. Well designed nonlinear types of PRNGs generally do not exhibit the type of predictable outcome more common with linear PRNGs. However, the drawback to such nonlinear generators is that they typically have higher complexity and require greater computational resources, thus making them less suitable for many systems. Therefore, the selection of the type of algorithm (linear versus nonlinear) raises issues related to computation resources available.
Another issue is the range of values possible. While it is theoretically possible to use a very large range of values, such as a range covered by 264, this tends to be expensive in practice because of the memory needed to store large numbers, particularly on systems that have lower computational requirements. In other words, the memory allocation is directly related to the possible size of the random number. For example, an 8-bit word (or 28 sized number) would have a range of values between 0 and 255. A 16-bit word (216 sized number) would have a range of values between 0 and 65,535 but will require twice the memory. Therefore, to save space, often a smaller range of values will be used but attempts will be made to make the selection of values within that range as random as possible.
Accordingly, to reduce costs, and to improve performance of the random number generator from a statistical perspective, it is desirable to obtain a number from a random number generator that is statistically likely to be selected anywhere within the possible range of values. Furthermore, it is desirable that PRNG has a large number of unique states so that it does not repeat itself for as long as possible; this is commonly referred to as a period of a PRNG. As can be appreciated, resolution of the issue regarding resource allocation versus statistical predictability versus period is often a compromise. Thus, a PRNG that can offer a different resolution to this issue would be appreciated.